home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / programming / c / gcc222-3.lha / const_class / dllist.ccp < prev    next >
Encoding:
Text File  |  1993-02-04  |  5.6 KB  |  339 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <values.h>
  23. #include <stream.h>
  24. #include <builtin.h>
  25. #include "<T>.DLList.h"
  26.  
  27. // error handling
  28.  
  29.  
  30.  
  31. void <T>DLList::error(const char* msg)
  32. {
  33.   (*lib_error_handler)("DLList", msg);
  34. }
  35.  
  36. int <T>DLList::length()
  37. {
  38.   int l = 0;
  39.   <T>DLListNode* t = h;
  40.   if (t != 0) do { ++l; t = t->fd; } while (t != h);
  41.   return l;
  42. }
  43.  
  44. <T>DLList::<T>DLList(const <T>DLList& a)
  45. {
  46.   if (a.h == 0)
  47.     h = 0;
  48.   else
  49.   {
  50.     <T>DLListNode* p = a.h;
  51.     <T>DLListNode* t = new <T>DLListNode(p->hd);
  52.     h = t;
  53.     p = p->fd;
  54.     while (p != a.h)
  55.     {
  56.       <T>DLListNode* n = new <T>DLListNode(p->hd);
  57.       t->fd = n;
  58.       n->bk = t;
  59.       t = n;
  60.         p = p->fd;
  61.     }
  62.     t->fd = h;
  63.     h->bk = t;
  64.     return;
  65.   }
  66. }
  67.  
  68. <T>DLList& <T>DLList::operator = (const <T>DLList& a)
  69. {
  70.   if (h != a.h)
  71.   {
  72.     clear();
  73.     if (a.h != 0)
  74.     {
  75.       <T>DLListNode* p = a.h;
  76.       <T>DLListNode* t = new <T>DLListNode(p->hd);
  77.       h = t;
  78.       p = p->fd;
  79.       while (p != a.h)
  80.       {
  81.         <T>DLListNode* n = new <T>DLListNode(p->hd);
  82.         t->fd = n;
  83.         n->bk = t;
  84.         t = n;
  85.         p = p->fd;
  86.       }
  87.       t->fd = h;
  88.       h->bk = t;
  89.     }
  90.   }
  91.   return *this;
  92. }
  93.  
  94. void <T>DLList::clear()
  95. {
  96.   if (h == 0)
  97.     return;
  98.  
  99.   <T>DLListNode* p = h->fd;
  100.   h->fd = 0;
  101.   h = 0;
  102.  
  103.   while (p != 0)
  104.   {
  105.     <T>DLListNode* nxt = p->fd;
  106.     delete(p);
  107.     p = nxt;
  108.   }
  109. }
  110.  
  111.  
  112. Pix <T>DLList::prepend(<T&> item)
  113. {
  114.   <T>DLListNode* t = new <T>DLListNode(item);
  115.   if (h == 0)
  116.     t->fd = t->bk = h = t;
  117.   else
  118.   {
  119.     t->fd = h;
  120.     t->bk = h->bk;
  121.     h->bk->fd = t;
  122.     h->bk = t;
  123.     h = t;
  124.   }
  125.   return Pix(t);
  126. }
  127.  
  128. Pix <T>DLList::append(<T&> item)
  129. {
  130.   <T>DLListNode* t = new <T>DLListNode(item);
  131.   if (h == 0)
  132.     t->fd = t->bk = h = t;
  133.   else
  134.   {
  135.     t->bk = h->bk;
  136.     t->bk->fd = t;
  137.     t->fd = h;
  138.     h->bk = t;
  139.   }
  140.   return Pix(t);
  141. }
  142.  
  143. Pix <T>DLList::ins_after(Pix p, <T&> item)
  144. {
  145.   if (p == 0) return prepend(item);
  146.   <T>DLListNode* u = (<T>DLListNode*) p;
  147.   <T>DLListNode* t = new <T>DLListNode(item, u, u->fd);
  148.   u->fd->bk = t;
  149.   u->fd = t;
  150.   return Pix(t);
  151. }
  152.  
  153. Pix <T>DLList::ins_before(Pix p, <T&> item)
  154. {
  155.   if (p == 0) error("null Pix");
  156.   <T>DLListNode* u = (<T>DLListNode*) p;
  157.   <T>DLListNode* t = new <T>DLListNode(item, u->bk, u);
  158.   u->bk->fd = t;
  159.   u->bk = t;
  160.   if (u == h) h = t;
  161.   return Pix(t);
  162. }
  163.  
  164. void <T>DLList::join(<T>DLList& b)
  165. {
  166.   <T>DLListNode* t = b.h;
  167.   b.h = 0;
  168.   if (h == 0)
  169.     h = t;
  170.   else if (t != 0)
  171.   {
  172.     <T>DLListNode* l = t->bk;
  173.     h->bk->fd = t;
  174.     t->bk = h->bk;
  175.     h->bk = l;
  176.     l->fd = h;
  177.   }
  178. }
  179.  
  180. int <T>DLList::owns(Pix p)
  181. {
  182.   <T>DLListNode* t = h;
  183.   if (t != 0 && p != 0)
  184.   {
  185.     do
  186.     {
  187.       if (Pix(t) == p) return 1;
  188.       t = t->fd;
  189.     } while (t != h);
  190.   }
  191.   return 0;
  192. }
  193.  
  194. void <T>DLList::del(Pix& p, int dir)
  195. {
  196.   if (p == 0) error("null Pix");
  197.   <T>DLListNode* t = (<T>DLListNode*) p;
  198.   if (t->fd == t)
  199.   {
  200.     h = 0;
  201.     p = 0;
  202.   }
  203.   else
  204.   {
  205.     if (dir < 0)
  206.     {
  207.       if (t == h)
  208.         p = 0;
  209.       else
  210.         p = Pix(t->bk);
  211.     }
  212.     else
  213.     {
  214.       if (t == h->bk)
  215.         p = 0;
  216.       else
  217.         p = Pix(t->fd);
  218.     }
  219.     t->bk->fd = t->fd;
  220.     t->fd->bk = t->bk;
  221.     if (t == h) h = t->fd;
  222.   }
  223.   delete t;
  224. }
  225.  
  226. void <T>DLList::del_after(Pix& p)
  227. {
  228.   if (p == 0)
  229.   {
  230.     del_front();
  231.     return;
  232.   }
  233.  
  234.   <T>DLListNode* b = (<T>DLListNode*) p;
  235.   <T>DLListNode* t = b->fd;
  236.  
  237.   if (b == t)
  238.   {
  239.     h = 0;
  240.     p = 0;
  241.   }
  242.   else
  243.   {
  244.     t->bk->fd = t->fd;
  245.     t->fd->bk = t->bk;
  246.     if (t == h) h = t->fd;
  247.   }
  248.   delete t;
  249. }
  250.  
  251. <T> <T>DLList::remove_front()
  252. {
  253.   if (h == 0)
  254.     error("remove_front of empty list");
  255.   <T>DLListNode* t = h;
  256.   <T> res = t->hd;
  257.   if (h->fd == h)
  258.     h = 0;
  259.   else
  260.   {
  261.     h->fd->bk = h->bk;
  262.     h->bk->fd = h->fd;
  263.     h = h->fd;
  264.   }
  265.   delete t;
  266.   return res;
  267. }
  268.  
  269.  
  270. void <T>DLList::del_front()
  271. {
  272.   if (h == 0)
  273.     error("del_front of empty list");
  274.   <T>DLListNode* t = h;
  275.   if (h->fd == h)
  276.     h = 0;
  277.   else
  278.   {
  279.     h->fd->bk = h->bk;
  280.     h->bk->fd = h->fd;
  281.     h = h->fd;
  282.   }
  283.   delete t;
  284. }
  285.  
  286. <T> <T>DLList::remove_rear()
  287. {
  288.   if (h == 0)
  289.     error("remove_rear of empty list");
  290.   <T>DLListNode* t = h->bk;
  291.   <T> res = t->hd;
  292.   if (h->fd == h)
  293.     h = 0;
  294.   else
  295.   {
  296.     t->fd->bk = t->bk;
  297.     t->bk->fd = t->fd;
  298.   }
  299.   delete t;
  300.   return res;
  301. }
  302.  
  303.  
  304. void <T>DLList::del_rear()
  305. {
  306.   if (h == 0)
  307.     error("del_rear of empty list");
  308.   <T>DLListNode* t = h->bk;
  309.   if (h->fd == h)
  310.     h = 0;
  311.   else
  312.   {
  313.     t->fd->bk = t->bk;
  314.     t->bk->fd = t->fd;
  315.   }
  316.   delete t;
  317. }
  318.  
  319.  
  320. int <T>DLList::OK()
  321. {
  322.   int v = 1;
  323.   if (h != 0)
  324.   {
  325.     <T>DLListNode* t = h;
  326.     long count = MAXLONG;      // Lots of chances to find h!
  327.     do
  328.     {
  329.       count--;
  330.       v &= t->bk->fd == t;
  331.       v &= t->fd->bk == t;
  332.       t = t->fd;
  333.     } while (v && count > 0 && t != h);
  334.     v &= count > 0;
  335.   }
  336.   if (!v) error("invariant failure");
  337.   return v;
  338. }
  339.